package org.xingole.daily;

/**
 * Problem Description: You are given a positive number n.
 * 
 * Return the smallest number x greater than or equal to n, such that
 * the binary representation of x contains only set bits.
 * 
 * A set bit refers to a bit in the binary representation of a number that has a value of 1.
 */
public class SmallestNumberWithAllSetBits {
    public int smallestNumber(int n) {
        /*
         * Hint: Find the strictly greater power of 2, and substract 1 from it.
         * 
         * Enumerate integers that contain only set bits: 1, 3, 7, 15. We can observer
         * that the pattern of this sequence is that each number is obtained by multiplying
         * the previous number by 2 and then adding 1.
         * 
         * We initialize x = 1. In each iteration of the loop, we update x as x = x * 2 + 1.
         * The loop continues until x becomes greater than or equal to n, and then we return
         * the result.
         */

         int x = 1;
         while (x < n) {
            x = x * 2 + 1;
         }

         return x;

    }
}
